1. Field of the Invention
This invention relates to the design of communications systems which employ adaptive filters. A method and device are disclosed which provides for the determination of the coefficients of adaptive filters with minimal computational complexity. Such methods and devices are particularly applicable for communications receivers operating in the presence of multipath interference.
2. Discussion of the Related Art
Adaptive filters are well known in the art. The coefficients of such filters are adjusted in dependence upon the characteristics of the received signal. This adjustment can be accomplished by transmitting a known training sequence of symbols to the receiver. The adjustment of the filter characteristics is effected by comparing the received symbols to the known transmitted symbols, so as to minimize the differences between the received and transmitted symbols. This adjustment is also termed equalization, because it has the effect of reducing, or equalizing, the effects of those environmental sources which caused the observed errors. After the adjustment, or training, of the receiver, the transmission of message symbols commences. The underlying assumption in this scenario is that the environmental conditions which caused differences in the received training symbols, compared to the transmitted training symbols, would affect the subsequent received message symbols as well, and, therefore, an adjustment to the filters which minimized errors in the received training symbols would also minimize errors in the received message symbols. As such, adaptive filters are well suited for eliminating relatively consistent interference. For example, the interference caused by the transmitted signal being reflected from surrounding structures and arriving at the receiver at slightly different times because of these reflections, or multiple paths, is relatively consistent, assuming the reflecting structures are stationary. Adaptive filters are very effective for removing the interference caused by these multiple path receptions.
In most environments, the training sequence is retransmitted periodically, to assure the correspondence of environmental conditions at the time of the training to the time of actual message reception. The period of time spent for the training will impact the overall efficiency of the communications channel, because the transmitter is unavailable for transmitting actual messages during the training period. The frequency of occurrence of such training periods is typically chosen based upon the likelihood of changes in the environmental conditions, as well as the tradeoffs between the efficiency of communication and the likelihood, and effect, of received errors. A communications channel which is subject to varying environmental conditions and which has a need for relatively error free communications will experience significant inefficiencies in using the training sequence technique for filter adaptation.
An alternative to filter adaptation based on a training sequence is to adapt the filter based upon the characteristics of the received, unknown, message symbols. This adaptation technique is termed blind equalization, because the actual transmitted symbols are unknown. Blind equalization techniques are particularly applicable when a series of transmitted signals have long-term characteristics which can be used to distinguish it from random noise. For example, a technique for encoding information into message symbols may be such that each of the possible symbols, over the long run, are equally likely to occur. Such an encoding will produce a distinctive pattern, such as might be characterized by its first, second, third, fourth, etc. statistical moments. If the received series of symbols is significantly different from the transmitted series, because of environmental effects between the transmitter and receiver, the received series will likely have a different set of statistical moments, caused by those symbols which were adversely affected by the environment. Blind equalization operates on the premise that if a filter can be adjusted to cancel, or equalize, the adverse environmental effects, the filtered series of symbols will exhibit the same long-term characteristics as the idealized, unknown, transmitted series of symbols. Conversely, adjusting a filter to produce the appropriate long-term characteristics from a received pattern, which contains the combination of the transmitted series having these long term characteristics together with adverse environmental effects, will have the effect of canceling the adverse environmental effects. To be effective, the iterative adjustment of the filter must be such that the filter converges to produce these idealized long-term characteristics, regardless of the particular characteristics of the environmental interference, within reasonable bounds.
Blind equalization techniques offer an advantage over training techniques in two regards: the equalization technique is applied to the actual message symbols, and no overhead is expended to transmit and process training symbols; and, the equalization technique can be applied continuously, so as to dynamically adapt to changing environmental conditions. In general, however, the blind equalization techniques require significantly more received symbols to converge to an equalized state.
In both the training technique and the blind equalization technique of adaptive filtering, the adjustment of the filter requires: a measure which represents the error content of a particular sample; a measure which represents a composite of these particular error measures, and is indicative of the quality of the received signal; and, a method of adjusting the filter which has the effect of minimizing the composite error measure, and thereby improving the quality of the filtered received signal. In the training technique, for example, the difference between the received symbol and the transmitted symbol is a measure of the particular error associated with that received symbol. A composite measure, or statistic, may be the average value of these errors. Such a composite, however, would not be truly representative of the quality of the received signal, because the positive and negative error measures would merely cancel each other. For this reason, other composite measures, such as the average magnitude of the errors, or the average square of the errors, is often utilized as a composite measure which is indicative of the received signal quality. The average square error is also known as the Mean Squared Error (MSE). A method which minimizes a Mean Squared Error measure is referred to as a Least Mean Square (LMS) method. For generality, the particular composite measure being minimized is termed the Cost Function, and the overall process is described as a cost minimization process.
In the blind equalization technique, the particular error measure is more difficult to define. Unlike as in the training technique, the particular transmitted symbol is unknown, and thus a direct comparison of the received symbol to the transmitted symbol cannot be performed to determine the error associated with each individual received symbol. As will be discussed, a commonly used error measure for communications systems is the CMA (Constant Modulus Algorithm), or Godard, error function [D. N. Godard, "Self-recovering Equalization and Carrier Tracking in Two-Dimensional Data Communication Systems," IEEE Trans. Commun., vol. COM-28, pp. 1867-1875, Nov. 1980]. This error measure involves a comparison of a characteristic of the received symbol (in this case, the square of its magnitude) to a target value, and a subsequent adjustment of the filter in dependence upon this comparison, multiplied by the received symbol value. The aforementioned long-term characteristics of the transmitted sequence are used to determine a target value which minimizes the cost function associated with this error function. As compared to the training technique, however, which requires one subtraction to compute the error measure, the Godard error measure requires three multiplications and one subtraction. Since the measure must be computed for each received symbol, these additional three multiplications per received symbol requires more processing time and higher hardware costs, and/or results in lower performance, as compared to the training technique of adaptive filtering.
One technique often employed to minimize the number of multiplications required for cost function minimization is to incrementally adapt the filter in dependence upon whether the characteristic of the received signal is above or below the target value, without regard to how far the characteristic was above or below the target. That is, the sign (positive/negative) of the error measure, and not its magnitude, is used as the error function for each received symbol. This less precise approach also allows for less complex operations to define the error measure. Minimization processes which employ signs are termed signed minimization processes, or hard-limiter minimization processes.
A hard-limiter alternative to the Godard error function has been developed, which eliminates the need to perform multiplications to compute the error measure for each received symbol [V. Weerackody et al, A Simple Hard-Limited Adaptive Algorithm for Blind Equalization, IEEE Trans. Circuits and Systems II: Analog and Digital Signal Processing, Vol. 39, No. 7, July 1992]. As will be discussed, however, this alternative does not provide an optimal solution, in that there is no target value which necessarily minimizes the cost function, even when the channel is perfectly equalized. Further, it can be shown that the appropriate choice of a target value is dependent upon the noise characteristics of the environment within which the receiver is operated. Thus, the designer of the system which employs this method must choose a target value based on an assumed environment, knowing that whatever value chosen is sub-optimal, and knowing that an environmental change will result in an indeterminable performance degradation.